1 // Equipo Poncho, Carriel y Ruana
22 template <class T
> string
toStr(const T
&x
)
23 { stringstream s
; s
<< x
; return s
.str(); }
24 template <class T
> int toInt(const T
&x
)
25 { stringstream s
; s
<< x
; int r
; s
>> r
; return r
; }
27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
29 #define D(x) cout << #x " = " << (x) << endl;
31 const double EPS
= 1e-9;
33 int cmp(double x
, double y
= 0, double tol
= EPS
) {
34 return (x
<= y
+ tol
) ? (x
+ tol
< y
) ? -1 : 0 : 1;
38 const int MAXB
= MAXN
* MAXN
;
50 cin
>> time_spent
[i
] >> balls
[i
];
51 totalBalls
+= balls
[i
];
53 for (int b
= 0; b
<= totalBalls
; ++b
) dp
[n
][b
] = 0;
54 for (int i
= n
- 1; i
>= 0; --i
) {
55 for (int b
= 0; b
<= totalBalls
; ++b
) {
56 dp
[i
][b
] = dp
[i
+ 1][b
+ balls
[i
]] + time_spent
[i
];
58 int option
= dp
[i
+ 1][b
- 1 + balls
[i
]] + time_spent
[i
] / 2;
59 if (option
< dp
[i
][b
]){
65 cout
<< dp
[0][0] << endl
;